import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;//已被使用的长度

    //做一个约定：初始化给个10个大小的int类型的数组，这里传进去的数组大小一定要一样大
    public TestHeap(){
        elem = new int[10];

    }

    //初始化数组
    //array数组的大小一定要为40个字节，做一个约定
    public void initElem(int[] array){
        for(int i = 0;i < array.length;i++){
            elem[i] = array[i];
            usedSize++;
        }
    }

    public void createHeap(){
        for(int parent = (usedSize - 1 -1) / 2;parent >= 0;parent--){
            shiftDown(parent,usedSize);
        }
    }

    /**
    *@Description:向下调整的代码
    *@Author:lxt
    *@Date:2023/10/24 15:08
    */
    private void shiftDown(int parent,int len){
        //找到左孩子结点的下标
        int child = 2 * parent + 1;
        while(child < len){//至少存在左孩子
            //比较左右孩子的大小
            //child + 1 < len是为了防止找右孩子的过程中越界
            if(child + 1 < len && elem[child] < elem[child + 1])
                child++;
            //父子结点的比较
            if(elem[child] > elem[parent]){
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                //如果有交换就要判断左子树或者右子树是不是也满足堆的要求
                parent = child;
                child = parent * 2 + 1;//找到左孩子的下标
            }else {
                break;
            }
        }
    }

    /**
    *@Description:向上调整的算法
    *@Author:lxt
    *@Date:2023/10/24 15:47
    */
    public void shiftUp(int child){
        //找到父结点
        int parent = (child - 1) / 2;
        while (child > 0){
            //如果孩子结点大于父结点，就交换
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                //父子结点的标记往上走
                child = parent;
                parent = (child - 1);
            }else {
                //如果没进入上面if，证明这个不用调整，是一个堆
                break;
            }
        }
    }

    //向堆插入元素
    public void offer(int val){
        if(isFull()){
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        //插到堆尾
        elem[usedSize++] = val;
        //开始向上调整
        shiftUp(usedSize - 1);
    }

    //判断是不是为满了
    public boolean isFull(){
        return usedSize == elem.length;
    }

    //写一个交换方法
    private void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //模拟优先队列，弹出堆顶元素后，重新再进行向下调整
    public void pop(){
        //先判断是否为空
        if(isEmpty()){
            return;
        }
        //如果不会空，代表要交换堆顶和最后一个结点
        swap(elem,0,usedSize - 1);
        usedSize--;
        //交换完后，进行向下调整
        shiftDown(0,usedSize);
    }

    //判断是否为空
    public boolean isEmpty(){
        return usedSize == 0;
    }

    //堆排序：不断让堆顶和最后一个结点交换，然后向下调整
    public void heapSort(){
        int end = usedSize - 1;
        while(end > 0){//下标为0的结点已经没有元素与之交换
            swap(elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }

}
